package com.lw.leetcode.str.b;

import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1239. 串联字符串的最大长度
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/14 13:43
 */
public class MaxLength {


    public static void main(String[] args) {
        MaxLength test = new MaxLength();


        // 输出：6
//        List<String> strings = Arrays.asList("cha", "r", "act", "ers");
        // 输出：4
//        List<String> strings = Arrays.asList("un","iq","ue");
        // 输出：0

        List<String> strings = Arrays.asList("yy","bkhwmpbiisbldzknpm");

        int i = test.maxLength(strings);
        System.out.println(i);
    }


    private int max = 0;
    private List<String> arr;
    private int[] nums;
    private int length;
    public int maxLength(List<String> arr) {
        this.arr = arr;
        this.length = arr.size();
        this.nums = new int[26];
        find(0, 0);
        return max;
    }

    private void find (int index, int count) {
        for (int i = index; i < length; i++) {
            String s = arr.get(i);
            if ("".equals(s)) {
                continue;
            }
            char[] chars = s.toCharArray();
            int flag = 0;
            int f = 0;
            for (char aChar : chars) {
                if(nums[aChar - 97] != 0) {
                    flag = 1;
                    break;
                }
                int v = 1 << (aChar - 97);
                if ((v & f) == v) {
                    flag = 1;
                    arr.set(i, "");
                    break;
                }
                f = f | v;
            }
            if (flag == 0) {
                for (char aChar : chars) {
                    nums[aChar - 97] = 1;
                }
                count += s.length();
                max = Math.max(max, count);
            }
            find(i + 1, count);
            if (flag == 0) {
                for (char aChar : chars) {
                    nums[aChar - 97] = 0;
                }
                count -= s.length();
            }
        }
    }

}
